package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC410 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 参考：https://leetcode-cn.com/problems/split-array-largest-sum/solution/er-fen-cha-zhao-by-liweiwei1419-4/
     * 题目和答案🐱啊，呱呱叫
     * @return:
     */
    public class Solution {

        public int splitArray(int[] nums, int m) {
            int max = 0;
            int sum = 0;

            // 计算「子数组各自的和的最大值」的上下界
            for (int num : nums) {
                max = Math.max(max, num);
                sum += num;
            }

            // 使用「二分查找」确定一个恰当的「子数组各自的和的最大值」，
            // 使得它对应的「子数组的分割数」恰好等于 m
            int left = max;
            int right = sum;
            while (left < right) {
                int mid = left + (right - left) / 2;

                int splits = split(nums, mid);
                if (splits > m) {
                    // 如果分割数太多，说明「子数组各自的和的最大值」太小，此时需要将「子数组各自的和的最大值」调大
                    // 下一轮搜索的区间是 [mid + 1, right]
                    left = mid + 1;
                } else {
                    // 下一轮搜索的区间是上一轮的反面区间 [left, mid]
                    right = mid;
                }
            }
            return left;
        }

        /***
         *
         * @param nums 原始数组
         * @param maxIntervalSum 子数组各自的和的最大值
         * @return 满足不超过「子数组各自的和的最大值」的分割数
         */
        private int split(int[] nums, int maxIntervalSum) {
            // 至少是一个分割
            int splits = 1;
            // 当前区间的和
            int curIntervalSum = 0;
            for (int num : nums) {
                // 尝试加上当前遍历的这个数，如果加上去超过了「子数组各自的和的最大值」，就不加这个数，另起炉灶
                if (curIntervalSum + num > maxIntervalSum) {
                    curIntervalSum = 0;
                    splits++;
                }
                curIntervalSum += num;
            }
            return splits;
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC410 an = new LC410();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
